package com.cdream.basic.algorithm.leetcode.array;

/**
 * @author cdream
 * @date 2021/10/19
 */
public class Question208 {
    class Trie {
        private Trie[] children;
        private boolean isEnd;

        /**
         * Initialize your data structure here.
         */
        public Trie() {
            children = new Trie[26];
            isEnd = false;
        }

        /**
         * Inserts a word into the trie.
         */
        public void insert(String word) {
            Trie cur = this;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                int index = c - 'a';
                Trie child = cur.children[index];
                if (child == null) {
                    cur.children[index] = new Trie();
                }
                cur = cur.children[index];
            }
            cur.isEnd = true;

        }

        /**
         * Returns if the word is in the trie.
         */
        public boolean search(String word) {
            Trie trie = getByPrefix(word);
            return trie!=null && trie.isEnd;
        }

        /**
         * Returns if there is any word in the trie that starts with the given prefix.
         */
        public boolean startsWith(String prefix) {
            return getByPrefix(prefix)!=null;
        }

        private Trie getByPrefix(String pre) {
            Trie trie = this;
            for (int i = 0; i < pre.length(); i++) {
                char c = pre.charAt(i);
                int index = c - 'a';
                trie = trie.children[index];
                if (trie==null){
                    return null;
                }
            }
            return trie;
        }
    }

}
